//归并法
double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
	int size = nums1.size() + nums2.size();
	vector<int> merge(size);
	int i = 0, j = 0, k = 0;
	for (; i < nums1.size() && j < nums2.size(); k++) {
		if (nums1[i] <= nums2[j])
			merge[k] = nums1[i++];
		else
			merge[k] = nums2[j++];
	}
	while (i < nums1.size())
		merge[k++] = nums1[i++];
	while (j < nums2.size())
		merge[k++] = nums2[j++];
	if (merge.size() % 2 == 0)
		return (double)(merge[size / 2] + merge[size / 2 - 1]) / 2;
	else
		return merge[size / 2];
}


//数组分割法
double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
	int m = nums1.size();
	int n = nums2.size();
	if (m > n)
		return findMedianSortedArrays(nums2, nums1);
	int left = 0, right = m;
	int totalLeft = (m + n + 1) / 2;
	//i表示分割线右边的元素，i-1表示分割线左边的元素
	while (left < right) {
		int i = (right + left + 1) / 2;
		int j = totalLeft - i;
		//是按照分割线进行划分，所以二分查找的两个数字相邻
		if (nums1[i - 1] > nums2[j])
			right = i - 1;
		else
			//当只有两个元素时会死循环，所以上面i要向上取整
			left = i;
	}
	//执行完之后，left = right
	int i = left;
	int j = totalLeft - i;
	int maxLeft1 = (i == 0) ? INT_MIN : nums1[i - 1];
	int minRight1 = (i == m) ? INT_MAX : nums1[i];
	int maxLeft2 = (j == 0) ? INT_MIN : nums2[j - 1];
	int minRight2 = (j == n) ? INT_MAX : nums2[j];

	if ((m + n) % 2 == 1)
		return max(maxLeft1, maxLeft2);
	else
		return (double)(max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2;
}


//二分查找法
double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
	int m = nums1.size();
	int n = nums2.size();
	int left = (m + n + 1) / 2;
	int right = (m + n + 2) / 2;
	return (findK(nums1, 0, nums2, 0, left) + findK(nums1, 0, nums2, 0, right)) / 2.0;
}

double findK(vector<int> a, int i, vector<int> b, int j, int k) {
	if (i >= a.size())
		return b[j + k - 1];
	if (j >= b.size())
		return a[i + k - 1];
	if (k == 1)
		return min(a[i], b[j]);
	int Amid = i + k / 2 - 1 < a.size() ? a[i + k / 2 - 1] : INT_MAX;
	int Bmid = j + k / 2 - 1 < b.size() ? b[j + k / 2 - 1] : INT_MAX;
	if (Amid < Bmid) {
		return findK(a, i + k / 2, b, j, k - k / 2);
	} else {
		return findK(a, i, b, j + k / 2, k - k / 2);
	}
}


